#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
class Solution {
public:
    int smallestDistancePair(std::vector<int>& nums, int k) {
        std::sort(nums.begin(), nums.end());
        int l = 0;
        int  n= nums.size();
        int r = nums[n-1]-nums[0];
        int ans = 0;
        int tmp = 0;
        while (l<=r)
        {
            int mid = l + ((r-l) >> 1);
            tmp=f(nums,mid);
            if (tmp>=k)
            {
                ans = mid;
                r = mid - 1;
            }else
            {
                l = mid + 1;
            }
        }
        return ans;
    }
    int f(std::vector<int>& nums, int limit)
    {
        int n = nums.size();
        int cnt = 0;
        for (int r = 1,l=0;r<n; r++)
        {
            
            while (l<r&& nums[r]-nums[l]>limit)
            {
                l++;
            }
            if (l!=r)
            cnt+=r-l;
        }
        return cnt;
    }
};
